package com.yulongtian.oneProblemEveryDay.month202302;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * https://leetcode.cn/problems/maximum-average-pass-ratio/
 *
 * @author yulongTian
 * @create 2023-02-19 9:33
 */
public class Test16 {
    public static void main(String[] args) {
        int[][] classes = {{1, 2}, {3, 5}, {2, 2}};
//        System.out.println((1.0) / 12 > (1.0) / 15);
        System.out.println(maxAverageRatio(classes, 2));
    }

    /**
     * 当你把一个学生加入课堂时，注意通过率的变化。
     * 如果你继续增加学生，通过率会发生什么变化？你给一个班级增加的学生越多，通过率的变化就越小。
     * <p>
     * 因为通过率的变化总是随着你增加的学生数量的增加而减少，
     * 那么你增加到每个班级的第一个学生就是通过率变化最大的那个。
     * <p>
     * 因为每个班级的通过率是平均加权的，所以总是最优的方法是把学生放在所有其他班级中变化最大的班级里。
     * <p>
     * 保持当前类大小的最大堆，并根据通过率的变化对它们进行排序。
     * 对于每个额外的学生，获取堆的顶部，更新类的大小，并将其放回堆中。
     *
     * @param classes
     * @param extraStudents
     * @return
     */
    //82 / 87 个通过测试用例
    public static double maxAverageRatio(int[][] classes, int extraStudents) {
        double total_rate = 0.0;
        int one_rate = 0;

        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                double temp1 = 1.0 * (o2[0] + 1) / (o2[1] + 1) - 1.0 * o2[0] / o2[1];
                double temp2 = 1.0 * (o1[0] + 1) / (o1[1] + 1) - 1.0 * o1[0] / o1[1];
                if (temp1 < temp2) {
                    return -1;
                } else if (temp1 > temp2) {
                    return 1;
                } else {
                    return 0;
                }
            }
        });

        for (int[] ints : classes) {
            if (ints[0] == ints[1]) {
                one_rate++;
                continue;
            }
            priorityQueue.add(ints);
        }

        if (priorityQueue.isEmpty()) {
            return 1.0;
        }

        while (extraStudents > 0) {
            int[] poll = priorityQueue.poll();
            poll[0] += 1;
            poll[1] += 1;
            priorityQueue.add(poll);
            extraStudents--;
        }

        while (!priorityQueue.isEmpty()) {
            int[] poll = priorityQueue.poll();
            total_rate += 1.0 * poll[0] / poll[1];
        }
        return (total_rate + one_rate) / classes.length;
    }

}
